//https://leetcode.cn/problems/word-search/
class Solution {
    boolean[][] visit;
    int row;
    int col;
    int[] dx;
    int[] dy;

    public boolean exist(char[][] board, String s) {
        row = board.length;
        col = board[0].length;
        visit = new boolean[row][col];
        dx = new int[] { -1, 1, 0, 0 };// x坐标 -> 上下左右
        dy = new int[] { 0, 0, -1, 1 };// y坐标 -> 上下左右
        boolean ret = false;
        //找第一个字符
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == s.charAt(0)) {
                    visit[i][j] = true;
                    if(dfs(board, i, j, s, 1)) {
                        return true;
                    }
                    //回溯
                    visit[i][j] = false;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int i, int j, String s, int pos) {
        if (pos == s.length())
            return true;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < row && y >= 0 && y < col && !visit[x][y] && board[x][y] == s.charAt(pos)) {
                visit[i + dx[k]][j + dy[k]] = true;
                if(dfs(board, x, y, s, pos + 1)) return true;
                //回溯
                visit[i + dx[k]][j + dy[k]] = false;
            }
        }
        //上下左右位置都没有该字符
        return false;
    }
}
